package 一些算法竞赛测试题;

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-10-02
 * Time: 12:06
 */

/*
解决全排列问题
 */
public class Demo8 {
    private static void DFS(int index, int n, int[] boxs, int[] book){
        //边界
        if(index == n){
            for(int x : boxs){
                System.out.print(x + " ");
            }
            System.out.println();
            return;
        }
        //尝试每一个可能
        for(int i = 1; i <= n; i++){
            if(book[i] == 0){
                boxs[index] = i;
                book[i] = 1;  //标记已经被使用
                DFS(index + 1, n, boxs, book);  //处理下一个盒子
                book[i] = 0;  //解除标记
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] boxs = new int[n];
        int[] book = new int[n + 1];
        DFS(0, n, boxs, book);
    }
}
